In a computer system which performs drawing operations on an output device, such as a computer display, video system, printer, or raster image processor (RIP), drawings are, in general, created by drawing commands, such as commands to draw a line, to draw a path (sequence of lines), to fill a path, to draw an image, to draw text, to fill a path with a gradient and the like. The content to be drawn is often artwork created by a designer, and a drawing application outputs the artwork using drawing commands available on the output device. A set of drawing commands available for an output device can be called a Page Description Language (PDL).
Drawing commands are applied on a drawing area, e.g., screen of a computer display or page of a printer. The sequence of drawing commands is in general divided at certain points where the drawing area is displayed or viewed, after which the drawing area is cleared and new drawing commands are applied independently of the previous drawing commands. These points can be called observation points. Certain optimizations only consider the state of the drawing area at each observation point (completed display image or completed page) rather than the state of the drawing area after each individual drawing command.
Within a sequence of drawing commands, a group of drawing commands can be used to form a more complex graphical element, like a company logo. In certain applications such complex graphical elements may be output repeatedly within a sequence of drawing commands.
The resolution of output devices (e.g., dots per inch, dpi) is ever increasing. Also the complexity of drawings is ever increasing, e.g., by the output devices offering color management, transparency, shading and the like, and by designers making more complex artwork. In general this results in ever increasing requirements on CPU speed and memory size. Optimizations to the rendering of drawing commands can be applied in order to reduce such hardware requirements.
Various approaches have been taken to optimize drawing commands.
A related art method for optimizing drawing commands is to cache drawing commands that occur multiple times. The drawing commands or the rendered/rasterized output produced by executing drawing commands are written to cache memory of the output device. When the drawing command recurs, repeated transmission or execution is avoided by using the cached data. See e.g., U.S. Pat. No. 6,441,918 (Hori, Fuji Xerox, about font caching). This method requires that cache worthy drawing commands are identified and that an optimized form of the drawing commands is stored in a cache.
Selecting cache worthy drawing commands can be done by the type of the drawing commands. E.g., see U.S. Pat. No. 8,416,249 (Ichieda, Seiko Epson) which discloses caching all drawing commands for image data. A drawback of this approach is that it is very coarse. There is no indication if an image will be reused, and therefore some images will be cached uselessly.
Another approach for selecting cache worthy drawing commands, e.g., U.S. Pat. No. 6,985,249 (Klassen, Xerox) identifies drawing commands and additionally evaluates drawing frequency, distance to the next occurrence, and processing cost of each drawing command. A drawback of this approach is that it only considers individual drawing commands and does not recognize groups of drawing commands that appear frequently together, and thereby misses some potential optimizations.
US Publication No. 2016/0179445 A1 (Bozier, Canon), for example, selects cache worthy drawing commands by recognizing consecutive sequences of repeating drawing commands. However, this approach still fails to recognize repeating groups of non-consecutive drawing commands where each group can be replaced by a single drawing command which has the same appearance as the group as a whole. Therefore this method still misses some potential to optimize by combining drawing commands, e.g., where reusable drawing commands are interspersed with non-reusable drawing commands.
Other approaches for selecting cache worthy drawing commands require that the creator mark drawing commands as reusable. This approach is often used in variable data printing, where the drawing commands are generated from a template, enabling the creator to easily identify which drawing commands will appear multiple times. The output device then only caches the drawing commands marked as reusable. For example, in U.S. Pat. No. 8,526,036 (Bellert, Konica Minolta), reusable data are marked as such using Personalized Print Markup Language (PPML). A similar approach is used by U.S. Pat. No. 6,330,071 (Vidyanand, EFI) where a printer driver outputs master pages containing reused drawing commands separately from variable content. A drawback of this approach is that it depends on the information provided by the creator of the drawing commands.
One method to allow the creator to identify drawing commands as reusable is to allow for drawing commands that group multiple drawing commands together. Such combined commands are known in display systems as surfaces (U.S. Pat. No. 8,527,563, Brugiolo, Microsoft) or layers (U.S. Pat. No. 5,748,174, Wong, VTech Electronics). In various page description languages for printers (PDLs) a set of drawing commands may be grouped together and the group of drawing commands may then be referenced multiple times, e.g., by PCL macros (see PCL5 Printer Language Technical Reference Manual, Hewlett-Packard Corporation, 1992), PostScript Forms (see PostScript Language Reference 2nd edition, Adobe Systems Inc., 1990, PostScript Language Reference 3rd edition, Adobe Systems Inc., 1999), AFP Overlays (Intelligent Printer Data Stream Reference, Sixth Edition, IBM Corporation, 2002) or PDF form XObjects (Portable Document Format Reference Manual 1.0, Adobe Systems 1993; PDF Reference second edition, Adobe Portable Document Format, Version 1.3, Adobe Systems 2000). This approach is used, e.g., by U.S. Pat. No. 6,919,967 (Pentecost, HP) which uses PCL macros to identify static page aspects and to create static page objects. The main drawback of all these approaches is that they rely on information prepared by the creator of the drawing commands and that the creator of the drawing commands must be aware of the trade-off between the optimization benefits and the overhead introduced by marking drawing commands as reusable.
U.S. Pat. No. 8,223,388 (Nakao, Fujifilm) describes a method where content previously marked as reusable is recognized as occurring at different locations on the same page. In contrast, the present invention combines the recognition of content as static/reusable with the recognition as occurring at different locations on the same page.